package com.zzh.tree;

import java.util.*;

public class No129_sumNumbers {
    public static void main(String[] args) {
        No129Solution solution = new No129Solution();
        int i = solution.sumNumbers(TreeNode.initTree());
        System.out.println(i);
    }
}
class No129Solution{
    private int sum;
    public int sumNumbers(TreeNode root) {
        if (root==null){
            return 0;
        }
        sum=0;
        dfs(root,new LinkedList<>());
        return sum;
    }
    private void dfs(TreeNode root, LinkedList<Integer> list){
        if (root.left==null&&root.right==null){
            list.offer(root.val);
            int[] ls=new int[list.size()];
            int a=0;
            for (Integer integer : list) {
                a *= 10;
                a += integer;
            }
            sum+=a;
//            sum+=Integer.parseInt(list.toArray());
//            System.out.println(Arrays.toString(list.toArray()));
            list.pollLast();
            return;
        }
        list.offer(root.val);
        if (root.left!=null){
            dfs(root.left,list);
        }
        if (root.right!=null){
            dfs(root.right,list);
        }
        list.pollLast();
    }
    //史诗级解答！
    /*
    * 充分运用了本题的出题特点
    * */
    private int helper(TreeNode root,int sum){
        if (root==null){
            return 0;
        }
        int temp=sum*10+root.val;
        if (root.left==null&&root.right==null){
            return temp;
        }
        return helper(root.left,temp)+helper(root.right,temp);
    }
}
